package com.mlamp.递归;

public class 反转部分链表节点 {

    public static void main(String[] args) {
        反转部分链表节点 instance = new 反转部分链表节点();

        Node head = null;
        Node curNode = null;
        for (int index = 1; index <= 5; index++) {
            Node newNode = new Node();
            newNode.next = null;
            newNode.data = index;
            if (head == null) {
                head = newNode;
            }
            if (curNode == null) {
                curNode = newNode;
            } else {
                curNode.next = newNode;
                curNode = newNode;
            }
        }
        Node p = head;
        while (p != null) {
            System.out.println(p.data);
            p = p.next;
        }
        System.out.println("--------------------------");
        Node node = instance.reversePartNodes(head, 2, 4);
        p = node;
        while (p != null) {
            System.out.println(p.data);
            p = p.next;
        }
    }

    private static final class Node {
        int data;
        Node next;
    }


    public Node reverseNode(Node head) {
        if (head == null || head.next == null) return head;
        Node node = reverseNode(head.next);
        Node t1 = head.next;
        t1.next = head;
        head.next = null;
        return node;
    }

    public Node reversePartNodes(Node head, int from, int to) {
        int cur = 1;
        Node preFromNode = null;
        Node fromNode = null;
        fromNode = head;
        while (fromNode != null && cur < from) {
            preFromNode = fromNode;
            fromNode = fromNode.next;
            cur++;
        }
        Node toNode = null;
        toNode = fromNode;
        while (toNode != null && cur < to) {
            toNode = toNode.next;
            cur++;
        }
        Node toNodeNext = toNode.next;
        toNode.next = null;
        Node node = reverseNode(fromNode);
        preFromNode.next = node;
        fromNode.next = toNodeNext;
        return head;
    }
}
